//题目:
// 给你一个整数数组 nums ，你可以对它进行一些操作。
// 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。
// 之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
// 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int deleteAndEarn(vector<int>& nums)
    {
        //题意转化————>用数组arr[i]表示i在nums中出现的总数(次数*值),对arr数组进行一次“打家劫舍”
        //由于“打家劫舍”永远不会捕获两个相邻的数，如:i、i+1、i-1,即如果捕获i,就不会再捕获i-1和i+1,故，符合题意

        //a.预处理
        //1.找出最大值
        int max_value=0;
        for(int i=0;i<nums.size();i++)
            max_value=max(max_value,nums[i]);
        //2.用数组arr[i]表示i在nums中出现的总数(次数*值)
        vector<int> arr(max_value+1,0);
        for(int i=0;i<nums.size();i++)
            arr[nums[i]]+=nums[i];
        //b.对arr数组进行“打家劫舍”
        //1.创建dp表————记录从初始位置(第一个元素或第二个元素)到第i个位置时的最大和
        vector<int> dp(max_value+1); 
        //2.初始化
        if(max_value==1)return arr[1];
        dp[0]=arr[0],dp[1]=arr[1],dp[2]=arr[2];
        //3.填表————动态转移方程：dp[i]=nums[i]+max(dp[i-2],dp[i-3]);
        for(int i=3;i<=max_value;i++)
            dp[i]=arr[i]+max(dp[i-2],dp[i-3]);
        //4.确定返回值
        return dp[max_value]>dp[max_value-1]?dp[max_value]:dp[max_value-1];
    }   
};